In the field of electronic commercial transactions, a guarantee that a certain operation will take a minimum amount of “time,” understood here as a number of computational steps, enables a variety of electronic commerce applications, for example, the timed release of a payment (e.g., a mortgage payment), and/or the fair exchange of information items such as a digital signature. This guarantee is particularly important between the exchange of two parties, i.e., a committing party and a receiving party, when there are no trusted parties acting as intermediaries. In this case, the guarantee insures that either both parties obtain each other's commitment information or neither party obtains the other's commitment information. When both parties receive each other's commitment information substantially concurrently, then electronic contract signing may be completed by the transfer of each party's digital signature. However, when contract negotiations are abruptly terminated for failures, either intentional or unintentional, that may occur in the transmission, one party may obtain a significant advantage over the other party by the failure to complete the communication.
A leading candidate operation for preventing one party from obtaining a significant advantage over the other party is the use of modular exponentiation in the commitment information. Modular exponentiation is a well-researched operation believed not well suited for parallelization, i.e., operations by multiple computers or computing systems substantially concurrently. Indeed, timed sequences based on modular exponentiation, where the next element in the sequence is obtained from raising the previous element to a certain power, has been taught in Rivest, et al., “Time-lock Puzzles and Timed-Release Crypto,” MIT/LCS/TR-683, 1996. Rivest teaches the construction of “time-lock puzzles” for encrypting data, where the goal is to design puzzles that are “intrinsically sequential.” In using time-lock puzzles, putting computers to work together in parallel does not speed up the finding a solution to the puzzle. Using a function similar to that of Rivest, Boneh and Naor (See, D. Boneh and M. Naor, “Timed Commitments (extended abstract),” Advances in Cryptology, CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, pages 236-254, Springer-Verlag, 2000) defined the notion of verifiable timed commitments as an extension to the standard notion of commitments in which a potential forced opening phase permits the receiving party to recover, with significant effort, the committed value without the help of the committing party. Boneh and Naor show how to use timed commitments to realize a variety of applications involving time, including timed signatures of a special kind, and, in particular, contract signing. Boneh and Naor also show how to exchange Rabin and RSA signatures when the respective moduli coincide with the one used to build the timed sequence.
Efficient Boneh and Naor time structure generation is proposed by Garay and Jakobsson (see, Garay and Jakobsson “Timed Release of Standard Digital Signatures,” Proceedings of Financial Cryptography '02, Matt Blaze (Ed.), volume 2357 of Lecture Notes in Computer Science, pages 168-182, Springer-Verlag, 2002). Garay and Jakobsson teach how to generate, and use, time structures or time-lines together with blinding techniques for the timed release of standard signatures.
A further improvement in the construction of time-line based on modular exponentiation, referred to as a “mirrored time-line,” is more fully disclosed in the concurrently-filed, co-pending related patent application Ser. No. 10/611,711, filed Jun. 30, 2003, entitled “Method and System for Fair Exchange of User Information” and in Garay and Pomerance, “Timed Fair Exchange of Standard Signatures,” Financial Cryptography '03, Rebecca Wright (Ed.), LNCS, Springer-Verlag (to appear), Gosier, Guadeloupe, January 2003. In this improved time-line construction, a protocol is disclosed that allows for the fair exchange of standard signatures, and further enables each receiving party to recover, with limited effort, the committed value without the help of the committing party.
An important requirement in the time structures discussed above is that the underlying sequence that comprises the structure does not cycle. That is, the period of the sequence is large enough that there are no repeated values in the sequence. Otherwise with a sequence that repeats, no guarantees could be given that a time-line would be traversed sequentially. That is if a repeated value is observed in the sequence, then the party computing the sequence can skip intermediate values and jump ahead to the next repetition(s). Such operations, referred to as cycle attacks, are known to be are possible when the sequence period is shorter than the total number of elements in the sequence.
Efforts have been made in estimating the period of more general sequences of the form gab for arbitrary g, a and b. See for example, Friedlander, et al., “Period of the Power Generator and Small Values of Carmichael's Function,” Math. Comp. 70 (2001), pp. 1591-1605 and Friedlander, et al.,“Small Values of the Carmichael Function and Cryptographic Applications,” Progress in Computer Science and Applied Logic, Vol. 20, pp. 25-232, Birkhäuser Verlag, Basel Switzerland, 2001. However, the period of sequences used in association with a timed release, timed commitment, timed fair exchange or “mirrored-time-line” has not been considered before.
Accordingly, there is a need for a method and system that allows for the selection of parameters that construct time-line sequences having periods that are large enough to limit cycle attacks on the time-line.